#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using ll = int64_t;

ll t,s,k1,k2,ans=std::numeric_limits<ll>::max();
std::vector<ll> f;
bool found = false;

template<class ...Ts>
void log(Ts&&...ts){
    // std::cout<<"Log:: ";
    // ((std::cout<<ts<<' '),...);
    // std::cout<<'\n';
}
/*

now = v1+v1*m1+v1*m1*m2...
=v1(1+m1+m1*m2)


*/ 

void dfs(ll now,ll time,ll nowv){
    if(now==ans){
        // log("at s","now",now,"time",time,"nowv",nowv);
    }
    if(found)return;
    if(time>=ans)return;
    if(now>=s){
        if(now!=s || time==1)return;
        ans=std::min(ans,time);
        // log("now",now,"time",time,"nowv",nowv);
        return;
    }
    // log("now",now,"time",time,"nowv",nowv);
    for(ll i=k2;i>=k1;i--){
        dfs(now+nowv*i,time+1,nowv*i);
    }
}

int main(){
    std::cin>>t;
    while(t--){
        std::cin>>s>>k1>>k2;
        log("s",s,"k1",k1,"k2",k2);
        ans=std::numeric_limits<ll>::max();
        found=false;
        f.clear();
        ll ns=s;
        f.push_back(1);
        while(ns!=1){
            for(ll i=2;i*i<=s;i++){
                if(ns%i==0){
                    f.push_back(i);
                    ns/=i;
                    goto next;
                }
            }
            f.push_back(ns);
            ns/=ns;
            next:;
        }
        log("f[i].start");
        for(ll i=0;i<f.size();i++){
            log("f[i]",f[i]);
        }
        log("f[i].end");
        if(ns!=0){
            f.push_back(ns);
        }
        log("f.size()",f.size());
        for(ll i=0;i<f.size();i++){
            dfs(f[i],1,f[i]);
        }
        std::cout<<(ans==std::numeric_limits<ll>::max()?-1:ans)<<'\n';
    }
}